COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\baselineskip 14pt
\line{\sevenrm a65.tex[154,mps] \today\hfill}
\parskip 6pt
\bigskip
\line{\bf Determinacy - Preserving Composition\hfill}

Let $M↓1$ be a machine with a single one-way output, and $M↓2$ a machine
with a single one-way input. We construct a machine, which we will call
the {\sl composition\/} $M↓1\circ M↓2$ of $M↓1$ and~$M↓2$, that has
$\tau\circ\tau↓2$ as its transfer relation. The idea of the
construction is that we perform a step of an $M↓1$ computation until
$M↓1$ prints a symbol. At that point, $M↓1\circ M↓2$ does not print the
symbol, but performs steps of $M↓2$ until $M↓2$ reads that symbol.

Suppose $x\tau↓1\tau↓2z$. Then there is some string $y=a↓1\ldots a↓n$, for which
$x\tau↓1y$ and $y\tau↓2z$. There is a computation of~$M↓1$ that reads~$x$
and writes~$y$; it can be segmented at the steps that write the
characters of~$y$:
$$c↓1w↓1c↓2w↓2\,\ldots\,c↓nw↓nc↓{n+1}$$
where $c↓i$ writes nothing and $w↓i$ is a single instruction that 
writes~$a↓i$. There is a computation of~$M↓2$ that reads~$y$ and writes~$z$;
it can be segmented at the steps that read the characters of~$y$:
$$d↓1r↓1d↓2r↓2\,\ldots\,d↓nr↓nd↓{n+1}$$
where $d↓i$ reads nothing and $r↓i$ is a single instruction that
reads~$a↓i$. Input operations tests may occur only as {\tt SCANs} in~$d↓i$
($1≤i≤n$) and as {\tt EOF} in~$d↓{n+1}$. We construct $M↓1\circ M↓2$
so that it has a computation 
$$c↓1w'↓1d↓1r'↓1\,\ldots\,c↓nw'↓nd↓nr'↓nc↓{n+1}d↓{n+1}\,,$$
where $w'↓i$ and $r'↓i$ omit the input and readperations respectively.

We use a new finite device, $B$, called a {\sl buffer}. During~$c↓i$,
$B={\Lambda}$; during $d↓i$, $B=a↓i$, except that during $d↓{n+1}$,
$B=e$.
The buffer is used to assure that $r↓i$ reads the same character that
$w↓i$ writes, and that the end-of-file tests are consistent with
the input. For each non-writing instruction $\pi$ of~$M↓1$, there is an
instruction of $M↓1\circ M↓2$:
$$(\pi,{\Lambda}→{\Lambda},{\tt NOOP})\,.$$
These perform steps of $c↓i$ so long as $B={\Lambda}$. For each writing
instruction ($\pi$, write~$a$) of~$M↓1$, there is an instruction of
$M↓1\circ M↓2$:
$$(\pi,{\Lambda}→a,{\tt NOOP})\,.$$
These, from which the $w'↓i$ are chosen, put $a$ into the buffer to begin
performing steps of~$M↓2$.

For each non-input instruction $\pi$ of~$M↓2$ there is an instruction of 
$M↓1\circ M↓2$:
$$({\tt NOOP},a→a,\pi)\,.$$
These perform steps of $d↓i$. 

For each instruction ($\pi$, scan $a$) of~$M↓2$, there is an
instruction of $M↓1\circ M↓2$:
$$({\tt NOOP},a→{\Lambda},\pi)\,.$$
These, from which the $r'↓i$ are chosen, remove $a$ from the buffer to
begin performing steps of~$M↓1$.

There is an instruction of $M↓1\circ M↓2$:
$$({\rm Accept}→{\rm Accept},{\Lambda}→e,{\tt NOOP})$$
that comes into play only when the computation of $M↓1$ is complete (all
of~$y$ has gone into~$B$) and $M↓2$ has consumed all of~$y$, leaving $B$
empty. By setting $B=e$, it disables scans and enables {\tt EOF}.

For each non-input instruction $\pi$ of~$M↓2$, there is an
instruction of $M↓1\circ M↓2$:
$$({\tt NOOP},e→e,\pi)\,.$$
These perform steps of $d↓{n+1}$. Tests of {\tt EOF} are omitted from~$\pi$,
being implied by~$e$ in the buffer.

It is clear that $M↓1\circ M↓2$ is deterministic if $M↓1$ and~$M↓2$ are.
Thanks to Richard Beigel for the idea of the method. Because $B$ is a
finite device, $B$~and all finite devices of~$M↓1$ and~$M↓2$ may be
combined into a single finite control in $M↓1\circ M↓2$.

\disleft 38pt::
{\bf Exercise.} If $M↓1$ has some instructions that write two-character
strings, and $M↓2$ has some instructions that read two-character strings,
how would you construct $M↓1\circ M↓2$?

\disleft 38pt::
Is $(M↓1\circ M↓2)\circ M↓3$ the same as $M↓1\circ(M↓2\circ M↓3)$?
Do they have the same IO relation?


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd

First draft October 9, 1987
Revised:  May 9, 1988
\bye